HW#4 --- last modified February 06 2019 04:07:35..

Solution set.

Due date: Apr 24

Files to be submitted:
  Hw4.zip

Purpose: To gain familiarity with space complexity, alternation, time-space trade-offs, and circuits.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO3 -- Show the completeness of a problem for one of our complexity classes.

LO5 -- Know conditions under which various of these hierarchies might collapse.

Specification:

For this homework I would like you to write up solutions to the problems below. If possible, write up the homework in LaTeX. If you use Word, format any math by using the math equation editor. Once you have prepared your solution output it as a PDF and submit it as Hw4.pdf. Be aware that the maximum-sized document that the upload system supports is 10 MB.

1. J. E. Hopcroft, W. J. Paul, and L. G. Valiant, "On time vs. space and related problems", Foundations of Computer Science, 1975, pp. 57-64, show that DTIME(`f(n)`) is contained in SPACE(`f(n)/log(f(n))`). The first part of their proof involves standardizing computations of `f(n)`-bounded Turing Machines so that they are block respecting. That is, the `k`-tapes of the TM are divided into blocks of size `sqrt(f(n))`, and the only times at which a tape head is allowed to move from one block to the next is at an integer multiples of time `sqrt(f(n))`. Show that any language in DTIME(`f(n)`) can be recognized by a block respecting TM in time `f(n)`.
2. A reduction `f(x)` is computable in logspace, if it has a read-only input tape, a write-only output tape, and read-write work-tapes, such that the amount of space used on the work-tapes is logarithmic. Show if `L_1` is logspace reducible to `L_2` then `L_1` is Karp reducible to `L_2`. Show the reduction of any NP language to TMSAT can be computed by a logspace reduction.
3. Let `(x,y) in A` be computable in `NP`. Suppose further that for every string `x` there exists a string `y` such that `|y| \leq p(|x|)` and `(x,y) in A`. Show that computing the lexicographically least string `y` such that `(x,y) in A` can be done in the polynomial hierarchy. Try to minimize the level of hierarchy.
4. Prove by induction `k` the following variant of Nepomnjasci's Theorem: For `k geq 1`, `0 < \epsilon < 1`, `TISP(n^{k(1-epsilon)}, n^{epsilon}) \subseteq \Sigma_{2k-1}-TIME(n)` (1.5pt). Conclude `L` is in the linear time hierarchy, `LINH = cup_k Sigma_k-TIME(n)` (1/2pt).
5. Prove that the graph of addition is in `NC^1`.

Point Breakdown